package a11_单调栈;

import java.util.Arrays;
import java.util.Stack;

/**
 * <p>
 * a05_柱状图中最大的矩形复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/4/9
 */
public class a05_柱状图中最大的矩形复习3 {
    public int largestRectangleArea(int[] heights) {
        int[] chars = new int[heights.length+2];
        System.arraycopy(heights, 0, chars, 1, heights.length);

        Stack<Integer> stack = new Stack<>();
        stack.add(0);


        int maxArea = 0;
        for (int i = 0; i < chars.length; i++) {
            while (!stack.isEmpty() && chars[stack.peek()] > chars[i]) {
                Integer pop = stack.pop();
                if(!stack.isEmpty()){
                    int w = i - stack.peek() - 1;
                    int h = chars[pop];
                    maxArea = Math.max(maxArea, w * h);
                }
            }
            stack.push(i);
        }

        return maxArea;
    }
}
